题目要求的是
i=1∑nk mod i
⇒i=1∑nk−⌊ik⌋∗i
⇒n∗k−i=1∑n⌊ik⌋∗i
然后 ,因为在l−r区间内⌊ik⌋的值相等,i递增,所以这段区间内是一个等差数列 ( 首项为 l∗⌊ik⌋ , 末项为 r∗⌊ik⌋ , 公差为 ⌊ik⌋ ) , 对于每一段区间计算和即可。
注意,Ans 计算的是∑i=1n⌊ik⌋∗i。
#include <cstdio>
#include <iostream>
using namespace std;
int n , k;
long long Ans;
int main( ) {
scanf("%d %d",&n,&k);
for( int l = 1 , r ; l <= n ; l = r + 1 ) {
r = k / l == 0 ? n : min( n , k / ( k / l ) );
Ans += 1ll * ( k / l ) * ( l + r ) * ( r - l + 1 ) / 2;
}
printf("%lld", 1ll * n * k - Ans );
return 0;
}